The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).

0 CpxTRS
↳1 DependencyGraphProof (BOTH BOUNDS(ID, ID), 13 ms)
↳2 CpxTRS
↳3 NestedDefinedSymbolProof (BOTH BOUNDS(ID, ID), 0 ms)
↳4 CpxTRS
↳5 CpxTrsToCdtProof (BOTH BOUNDS(ID, ID), 0 ms)
↳6 CdtProblem
↳7 CdtLeafRemovalProof (BOTH BOUNDS(ID, ID), 0 ms)
↳8 CdtProblem
↳9 CdtUsableRulesProof (⇔, 0 ms)
↳10 CdtProblem
↳11 CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)), 151 ms)
↳12 CdtProblem
↳13 CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)), 27 ms)
↳14 CdtProblem
↳15 CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)), 161 ms)
↳16 CdtProblem
↳17 SIsEmptyProof (BOTH BOUNDS(ID, ID), 0 ms)
↳18 BOUNDS(1, 1)

(0) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

a(h, h, h, x) → s(x)
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(l, s(x), h, z) → a(l, x, z, z)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))
s(h) → 1
app(nil, k) → k
app(l, nil) → l
app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))

Rewrite Strategy: INNERMOST

(1) DependencyGraphProof (BOTH BOUNDS(ID, ID) transformation)

The following rules are not reachable from basic terms in the dependency graph and can be removed:
+(s(x), s(y)) → s(s(+(x, y)))
+(+(x, y), z) → +(x, +(y, z))

(2) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

a(l, x, s(y), h) → a(l, x, y, s(h))
sum(cons(x, nil)) → cons(x, nil)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
app(cons(x, l), k) → cons(x, app(l, k))
app(nil, k) → k
app(l, nil) → l
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))
a(h, h, h, x) → s(x)
a(l, s(x), h, z) → a(l, x, z, z)
s(h) → 1

Rewrite Strategy: INNERMOST

(3) NestedDefinedSymbolProof (BOTH BOUNDS(ID, ID) transformation)

The following defined symbols can occur below the 0th argument of sum: s, a
The following defined symbols can occur below the 0th argument of a: s, a
The following defined symbols can occur below the 1th argument of a: s, a

Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
a(l, x, s(y), h) → a(l, x, y, s(h))
a(l, x, s(y), s(z)) → a(l, x, y, a(l, x, s(y), z))

(4) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2).


The TRS R consists of the following rules:

app(cons(x, l), k) → cons(x, app(l, k))
sum(cons(x, nil)) → cons(x, nil)
a(s(l), h, h, z) → a(l, z, h, z)
+(x, h) → x
+(h, x) → x
app(nil, k) → k
app(l, nil) → l
a(h, h, h, x) → s(x)
a(l, s(x), h, z) → a(l, x, z, z)
sum(cons(x, cons(y, l))) → sum(cons(a(x, y, h, h), l))
s(h) → 1

Rewrite Strategy: INNERMOST

(5) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

Converted Cpx (relative) TRS to CDT

(6) Obligation:

Complexity Dependency Tuples Problem
Rules:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
+(z0, h) → z0
+(h, z0) → z0
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
APP(nil, z0) → c1
APP(z0, nil) → c2
SUM(cons(z0, nil)) → c3
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(h, h, h, z0) → c6(S(z0))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
+'(z0, h) → c8
+'(h, z0) → c9
S(h) → c10
S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
APP(nil, z0) → c1
APP(z0, nil) → c2
SUM(cons(z0, nil)) → c3
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(h, h, h, z0) → c6(S(z0))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
+'(z0, h) → c8
+'(h, z0) → c9
S(h) → c10
K tuples:none
Defined Rule Symbols:

app, sum, a, +, s

Defined Pair Symbols:

APP, SUM, A, +', S

Compound Symbols:

c, c1, c2, c3, c4, c5, c6, c7, c8, c9, c10

(7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

Removed 7 trailing nodes:

+'(z0, h) → c8
APP(nil, z0) → c1
SUM(cons(z0, nil)) → c3
+'(h, z0) → c9
S(h) → c10
A(h, h, h, z0) → c6(S(z0))
APP(z0, nil) → c2

(8) Obligation:

Complexity Dependency Tuples Problem
Rules:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
+(z0, h) → z0
+(h, z0) → z0
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
K tuples:none
Defined Rule Symbols:

app, sum, a, +, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(9) CdtUsableRulesProof (EQUIVALENT transformation)

The following rules are not usable and were removed:

app(cons(z0, z1), z2) → cons(z0, app(z1, z2))
app(nil, z0) → z0
app(z0, nil) → z0
sum(cons(z0, nil)) → cons(z0, nil)
sum(cons(z0, cons(z1, z2))) → sum(cons(a(z0, z1, h, h), z2))
+(z0, h) → z0
+(h, z0) → z0

(10) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
S tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
K tuples:none
Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x1, x2, x3, x4)) = 0   
POL(APP(x1, x2)) = x1   
POL(SUM(x1)) = x1   
POL(a(x1, x2, x3, x4)) = 0   
POL(c(x1)) = x1   
POL(c4(x1, x2)) = x1 + x2   
POL(c5(x1)) = x1   
POL(c7(x1)) = x1   
POL(cons(x1, x2)) = [1] + x1 + x2   
POL(h) = 0   
POL(s(x1)) = 0   

(12) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
S tuples:

A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x1, x2, x3, x4)) = x1   
POL(APP(x1, x2)) = 0   
POL(SUM(x1)) = x1   
POL(a(x1, x2, x3, x4)) = [1] + x4   
POL(c(x1)) = x1   
POL(c4(x1, x2)) = x1 + x2   
POL(c5(x1)) = x1   
POL(c7(x1)) = x1   
POL(cons(x1, x2)) = [1] + x1 + x2   
POL(h) = 0   
POL(s(x1)) = [1] + x1   

(14) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
S tuples:

A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)) transformation)

Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.

A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
We considered the (Usable) Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
And the Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
The order we found is given by the following interpretation:
Polynomial interpretation :

POL(1) = 0   
POL(A(x1, x2, x3, x4)) = [1] + x2 + [2]x4 + x42 + x1·x4   
POL(APP(x1, x2)) = x1·x2   
POL(SUM(x1)) = x1   
POL(a(x1, x2, x3, x4)) = [1] + [2]x4   
POL(c(x1)) = x1   
POL(c4(x1, x2)) = x1 + x2   
POL(c5(x1)) = x1   
POL(c7(x1)) = x1   
POL(cons(x1, x2)) = [2] + x1 + x2   
POL(h) = 0   
POL(s(x1)) = [1] + [2]x1   

(16) Obligation:

Complexity Dependency Tuples Problem
Rules:

a(s(z0), h, h, z1) → a(z0, z1, h, z1)
a(h, h, h, z0) → s(z0)
a(z0, s(z1), h, z2) → a(z0, z1, z2, z2)
s(h) → 1
Tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
S tuples:none
K tuples:

APP(cons(z0, z1), z2) → c(APP(z1, z2))
SUM(cons(z0, cons(z1, z2))) → c4(SUM(cons(a(z0, z1, h, h), z2)), A(z0, z1, h, h))
A(s(z0), h, h, z1) → c5(A(z0, z1, h, z1))
A(z0, s(z1), h, z2) → c7(A(z0, z1, z2, z2))
Defined Rule Symbols:

a, s

Defined Pair Symbols:

APP, SUM, A

Compound Symbols:

c, c4, c5, c7

(17) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)

The set S is empty

(18) BOUNDS(1, 1)